package promote.brozen.algorithm.leetcode._042;

import java.util.ArrayList;
import java.util.List;

/**
 * https://leetcode-cn.com/problems/trapping-rain-water/
 *
 * @author Brozen
 * @date 2020/6/5 9:34 AM
 * @email brozen@qq.com
 */
public class TrappingRainWater {

    public int trap(int[] height) {
        return rain(height, 0, false, height.length - 1, false);
    }


    private static int rain(int[] arr, int leftIdx, boolean leftBlocked, int rightIdx, boolean rightBlocked) {
        if (rightIdx - leftIdx <= 1) {
            return 0;
        }

        if (leftBlocked && rightBlocked) {
            int width = rightIdx - leftIdx - 1;
            int height = Math.min(arr[leftIdx], arr[rightIdx]);
            int area = width * height;
            for (int i = leftIdx + 1; i < rightIdx; i++) {
                area -= arr[i];
            }
            return area;
        } else if (leftBlocked) {
            List<Integer> maxIndices = findMaxHeightIndices(arr, leftIdx + 1, rightIdx);
            if (maxIndices.isEmpty()) {
                return 0;
            }

            int area = 0;
            int left = leftIdx;
            int right;
            rightBlocked = true;
            for (Integer idx : maxIndices) {

                right = idx;
                area += rain(arr, left, true, right, true);
                left = right;
            }

            area += rain(arr, left, true, rightIdx, false);

            return area;
        } else if (rightBlocked) {
            List<Integer> maxIndices = findMaxHeightIndices(arr, leftIdx, rightIdx - 1);
            if (maxIndices.isEmpty()) {
                return 0;
            }

            int area = 0;
            int left = leftIdx;
            int right;
            leftBlocked = false;
            for (Integer maxIndex : maxIndices) {
                right = maxIndex;
                area += rain(arr, left, leftBlocked, right, true);
                leftBlocked = true;
                left = right;
            }


            area += rain(arr, left, true, rightIdx, true);

            return area;
        } else {
            List<Integer> maxIndices = findMaxHeightIndices(arr, leftIdx, rightIdx);
            if (maxIndices.isEmpty()) {
                return 0;
            }

            int area = 0;
            int left = leftIdx;
            int right;
            leftBlocked = false;
            for (Integer idx : maxIndices) {
                right = idx;
                area += rain(arr, left, leftBlocked, right, true);

                leftBlocked = true;
                left = right;
            }

            area += rain(arr, left, true, rightIdx, false);

            return area;
        }
    }

    // 找到 leftIdx <= i <= rightIdx 中间最大的数字的索引
    private static List<Integer> findMaxHeightIndices(int[] arr, int leftIdx, int rightIdx) {
        List<Integer> indices = new ArrayList<>();
        int maxValue = 1;
        for (int i = leftIdx; i <= rightIdx; i++) {
            if (arr[i] > maxValue) {
                indices.clear();
                indices.add(i);
                maxValue = arr[i];
            } else if (arr[i] == maxValue) {
                indices.add(i);
            }
        }
        return indices;
    }

}
